//
// Created by admin on 2020/7/17.
//

#include "demo.h"
/*
 * 初始化一个结点，作为队列的头尾指针指向的头尾结点(也就是初始化时，头尾指针指向的是同一块空间)；
 * 将结点的后继初始化为空；
 * 时间复杂度:O(1)
 * 空间复杂度:O(1)
 */
LinkQueue InitQueue(){
    LinkQueue linkQueue;
    linkQueue.head = linkQueue.tail = (QueuePtr)malloc(sizeof(QNode));
    if (!linkQueue.head){
        exit(0);
    } else{
        linkQueue.head->next = NULL;
        return linkQueue;
    }
}

/*
 * 遍历队列，当队头指针指向的头结点为空时，意味着销毁完毕，结束遍历；
 * 将队头指针指向的结点的后继提出；
 * 释放队头指针指向的结点；
 * 将队头指针指向提出的结点；
 * 判断队头指针指向的头结点是否为空；
 * 若不为空，则继续操作；
 * 若为空，则结束操作；
 * 时间复杂度:O(n)
 * 空间复杂度:O(1)
 */
void DestroyQueue(LinkQueue *S){
    while (S->head){
        QueuePtr P = S->head->next;
        free(S->head);
        S->head = P;
//        //节约空间，使用尾指针；
//        (*S).tail = (*S).head;
//        free((*S).head);
//        (*S).head = (*S).tail;
    }
    S->tail = NULL;
}

/*
 * 当队列未被销毁时；
 * 遍历队列，当队头指针指向的头结点的后继为空时，意味着到达队尾，结束遍历；
 * 将队头指针指向的结点的后继提出；
 * 释放队头指针指向的结点；
 * 将队头指针指向提出的结点；
 * 判断队头指针指向的头结点是否为空；
 * 若不为空，则继续操作；
 * 若为空，则结束操作；
 * 时间复杂度:O(n)
 * 空间复杂度:O(1)
 */
void ClearQueue(LinkQueue *S){
    if (!S->head) {
        printf("Queue Is Destroyed!");
    }else {
        while (S->head->next) {
            QueuePtr P = S->head->next;
            free(S->head);
            S->head = P;
        }
    }
}

/*
 * 当队列未被销毁时；
 * 初始化长度标记为0；
 * 从队头指针指向的头结点的后继开始遍历；
 * 每遍历一次，初始化长度标记加一；
 * 当后继为空，意味着计算完毕，结束遍历；
 * 时间复杂度:O(n)
 * 空间复杂度:O(1)
 */
int QueueLength(LinkQueue S){
    if (!S.head) {
        printf("Queue Is Destroyed!");
    }else {
        int length = 0;
        while (S.head->next) {
            S.head = S.head->next;
            length++;
        }
        return length;
    }
}
/*
 * 当队列未被销毁时；
 * 向内存申请一块空间，存储数据；
 * 将空间的后继设为队列尾指针指向的尾结点的后继；
 * 将队列尾指针指向此空间的地址；
 * 时间复杂度:O(1)
 * 空间复杂度:O(1)
 */
int EnQueue(LinkQueue *S,int data){
    if (!S->head) {
        printf("Queue Is Destroyed!");
        return 0;
    }
    QueuePtr P = (QueuePtr)malloc(sizeof(QNode));
    if (!P){
        exit(0);
    } else{
        P->data = data;
        P->next = S->tail->next;
        S->tail->next = P;
        S->tail = P;
        return 1;
    }
}

/*
 * 当队列未被销毁时；
 * 当队列头尾指针指向的头尾结点不一致时；
 * 取出头指针指向的头结点的后继P；
 * 将数据data取出；
 * 将头指针指向的头结点的后继更新为P的后继；
 * 如果P等于尾指针指向的尾结点时，将头结点赋值给尾结点(防止尾结点丢失)；
 * 释放P;
 * 返回data;
 * 时间复杂度:O(1)
 * 空间复杂度:O(1)
 */
int DeQueue(LinkQueue *S){
    if (!S->head) {
        printf("Queue Is Destroyed!");
    }else if (S->head != S->tail){
        QueuePtr P = S->head->next;
        int data = P->data;
        S->head->next  = P->next;
        if (S->tail == P){
            S->tail = S->head;
        }
        free(P);
        return data;
    } else{
        printf("Queue Is Empty!");
    }
}
/*
 * 当队列未被销毁时；
 * 当队列的头指针指向的头结点存在后继时；
 * 取出头指针指向的头结点的后继的数据并返回；
 * 时间复杂度:O(1)
 * 空间复杂度:O(1)
 */
int GetHead(LinkQueue S){
    if (!S.head) {
        printf("Queue Is Destroyed!");
    }else if (S.head->next){
        return S.head->next->data;
    } else{
        printf("Queue Is Empty!");
    }
}